package arrays;

/**
 * @author pengfei.hpf
 * @date 2020/3/17
 * @verdion 1.0.0
 * 41. 缺失的第一个正数
 * 给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
 *
 * 示例 1:
 *
 * 输入: [1,2,0]
 * 输出: 3
 * 示例 2:
 *
 * 输入: [3,4,-1,1]
 * 输出: 2
 * 示例 3:
 *
 * 输入: [7,8,9,11,12]
 * 输出: 1
 * 说明:
 *
 * 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
 */
public class FirstMissingPositive {
    public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length == 0){
            return 1;
        }
        int n = nums.length + 1;
        int index = 0;
        while(index < n - 1){
            int num = nums[index];
            //TODO: inplace 思想
            while(num <= n - 1 && num > 0 && nums[num - 1] != nums[index]){
                int temp =  nums[num - 1];
                nums[num - 1] = num;
                nums[index] = temp;
                num = temp;
            }
            index ++;
        }
        int i = 0;
        for(; i < nums.length; i ++){
            if(nums[i] != i + 1){
                break;
            }
        }
        return i + 1;
    }
}
